#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
    int val;
    struct ListNode* next;
};
int main()
{
	struct ListNode* s1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (s1 == NULL)
	{
		perror("malloc");
		return 1;
	}
	struct ListNode* s2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (s2 == NULL)
	{
		perror("malloc");
		return 1;
	}
	struct ListNode* s3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (s3 == NULL)
	{
		perror("malloc");
		return 1;
	}
	struct ListNode* s4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (s4 == NULL)
	{
		perror("malloc");
		return 1;
	}
	struct ListNode* s5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (s5 == NULL)
	{
		perror("malloc");
		return 1;
	}
	s1->val = 1;
	s2->val = 2;
	s3->val = 3;
	s4->val = 4;
	s5->val = 5;
	s1->next = s3;
	s2->next = s4;
	s3->next = s5;
	s4->next = NULL;
	s5->next = NULL;
	struct ListNode* newHead = NULL;
	struct ListNode* newTail = NULL;
	struct ListNode* l1 = s1;
	struct ListNode* l2 = s2;
	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			if (newHead == NULL)
			{
				newHead = newTail = l1;
			}
			else
			{
				newTail->next = l1;
				newTail = newTail->next;
			}
			l1 = l1->next;
		}
		else {
			if (newHead == NULL)
			{
				newHead = newTail = l2;
			}
			else
			{
				newTail->next = l2;
				newTail = newTail->next;
			}
			l2 = l2->next;
		}

	}
	if (l2)
	{
		newTail->next = l2;
	}
	if (l1)
	{
		newTail->next = l1;
	}
	while (newHead)
	{
		printf("%d->", newHead->val);
		newHead = newHead->next;
	}
	free(s1);
	free(s2);
	s1 = NULL;
	s2 = NULL;
	return 0;
}